package DataStructure.tree;

import java.util.PriorityQueue;
//哈夫曼树
public class HuffmanTree {
    private Node root;

    private static class Node{
        private char e;
        private double w;//权值
        private Node left;
        private Node right;
        public Node(char e, double w,Node left, Node right) {
            this.e=e;
            this.w=w;
            this.left=left;
            this.right=right;
        }
    }
    public HuffmanTree(double[] weight) {
        build(weight);
    }

    private void build(double[] weight) {
        PriorityQueue<Node> pq=new PriorityQueue<>((o1, o2) -> {
            double cmp=o1.w-o2.w;
            return cmp>0?1:cmp<0?-1:0;
        });
        for (int i = 0; i < weight.length; i++) {
            pq.add(new Node((char) ('a'+i),weight[i],null,null));
        }
        while (pq.size()>=2){
            Node n1=pq.poll();
            Node n2=pq.poll();
            Node n3=new Node('_',n1.w+n2.w,n1,n2);//空节点
            pq.add(n3);
        }
        root=pq.poll();

    }
    public void show(){
        show("",root);
    }
    private void show(String code,Node n){
        if(n==null)
            return;
        show(code+"0",n.left);
        show(code+"1",n.right);
        if(n.e=='_')
            return;
        System.out.println(n.e+":"+code);
    }

}
